#include <stdio.h>
#include <stdlib.h>

struct s_heap
{
  int *head;
  size_t size;
};

int heaparray[100];
int size = 0;

inline void
heap_swap(int pos1, int pos2)
{
  int tmp;
  tmp = heaparray[pos1];
  heaparray[pos1] = heaparray[pos2];
  heaparray[pos2] = tmp;

  return;
}

void
heap_bubble_down(int pos)
{

  int l = size;

  int childpos;
  if (l <= (2 * pos + 1))
    { // leaf
      return;

    }
  else if (l == (2 * pos + 2))
    { // one child

      childpos = 2 * pos + 1;

      if (heaparray[childpos] <= heaparray[pos])
        return;

    }
  else
    { // two child

      int lpos = 2 * pos + 1;
      int rpos = lpos++; // 2 * pos + 2

      int leftchild = heaparray[lpos];
      int rightchild = heaparray[rpos];

      int root = heaparray[pos];
      if (leftchild <= root && rightchild <= root)
        return;

      childpos = (leftchild > rightchild) ? lpos : rpos;
    }

  heap_swap(childpos, pos);
  heap_bubble_down(childpos);
}

inline int
heap_parentpos(int child)
{

  if (child == 1 || child == 2)
    return 0;

  // if child is an odd number, then it's a left child;
  // if it's even, then it's a right child.
  if (child % 2 == 0)
    return (child - 2) / 2;
  else
    return (child - 1) / 2;
}

void
heap_bubble_up(int pos)
{

  if (pos == 0)
    return;

  int parentpos = heap_parentpos(pos);
  if (heaparray[pos] > heaparray[parentpos])
    {
      heap_swap(parentpos, pos);
      heap_bubble_up(parentpos);
    }
}

void
heap_insert(int val)
{
  // to insert, append the new value to the end,
  // and then bubble it up to its correct position.

  heaparray[size] = val;
  heap_bubble_up(size);
  size++;
}

int
heap_remove_largest()
{
  // to remove largest, store the largest, insert the
  // last element into its position, and then bubble it
  // down.

  int result;
  result = heaparray[0];

  // move forward array
  size--;
  heaparray[0] = heaparray[size];

  heap_bubble_down(0);

  return result;
}

void
heap__pretty_print_line(int pos, int indent)
{

  int i;
  int childpos;

  if (size == 0)
    {
      printf("<EMPTY!>");
      return;
    }

  for (i = 0; i < indent; i++)
    printf("    ");

  printf("%3d\n", heaparray[pos]);

  int l = size;
  if (l <= (2 * pos + 1))
    { // leaf
    }
  else if (l == (2 * pos + 2))
    { // one child

      childpos = 2 * pos + 1;
      heap__pretty_print_line(childpos, indent + 1);
    }
  else
    { // two child

      childpos = 2 * pos + 1;
      heap__pretty_print_line(childpos, indent + 1);

      childpos = 2 * pos + 2;
      heap__pretty_print_line(childpos, indent + 1);
    }
}

void
heap_print()
{
  heap__pretty_print_line(0, 0);
}
